//定义bfs使用的基础节点，基础节点提供派生类必须实现的接口
function baseNode() {
    this.parent = null;  //上一节点
    this.actionDesc = "" //动作描述,描述了上一节点通过什么样的方式变化为该节点
}

//获取该节点的所有变化节点
baseNode.prototype.getNextStates = function() {
    throw 'baseNode.getNextStates: 你的派生类必须实现它';
}

//判断两个节点是否相等
baseNode.prototype.equal = function(node) {
    throw 'baseNode.equal: 你的派生类必须实现它';
}

//输出调试信息
baseNode.prototype.dump = function() {
    throw 'baseNode.dump: 你的派生类必须实现它';
}

//获得唯一标识
baseNode.prototype.id = function() {
    throw 'baseNode.id: 你的派生类必须实现它';
}

var maxLoopCount = 0 //防止死循环
function setBfsMaxLoop(count)
{
    maxLoopCount = count
}
/** 
 * 广度优先搜索 
 * @param Vs 起点 
 * @param Vd 终点 
 * @param callback 算法结束处理 
 */  
//参考: https://blog.csdn.net/g11d111/article/details/76169861
function bfsAsync(vs, vd, callback) {
    let blacklist = {};
    let graylist = [];

    //初始状态将起点放进队列Q  
    graylist.push(vs);
    //设置节点已经访问过了！
    blacklist[vs.id()] = vs;

    async function* bfsGenerator(graylist, blacklist, vd) {
        let count = 0;
        while (graylist.length > 0) { // 队列不为空，继续搜索！
            if (maxLoopCount > 0 && count > maxLoopCount) {
                console.info('达到最大循环次数');
                break;
            }
            count++;
            // 取出队列的头Vn
            // 并从队列中移除
            let vn = graylist.shift();

            let states = vn.getNextStates();
            for (let vw of states) { // Vw = Vn通过某规则能够到达的节点
                if (!(vw.id() in blacklist)) {
                    // Vw是一个合法的节点并且为白色节点
                    vw.parent = vn;
                    graylist.push(vw); // 加入队列Q
                    blacklist[vw.id()] = vw; // 设置节点颜色
                }
                let findEnd = vw.equal(vd);
                yield [count, vw, findEnd];
                if (findEnd) { // 找到终点了！
                    return;
                }
            }
            // Avoid blocking the event loop
            await new Promise(resolve => setTimeout(resolve, 0));
        }
    }

    (async () => {
        let trace = null;
        for await (let [count, vw, findEnd] of bfsGenerator(graylist, blacklist, vd)) {
            // 处理生成的节点
            let nodeinfo = vw.dump();
            console.log('count=', count, 'vw=', nodeinfo);
            if (findEnd) { // 找到终点了！（最后一个节点）
                // 把路径记录
                trace = [];
                let p = vw;
                while (p) {
                    trace.push(p);
                    p = p.parent;
                }
                trace.reverse();
                console.log('结果:');
                for (let v of trace) {
                    console.log(v.dump());
                }
            }
        }
        callback(trace);
    })();

    //bfs函数是立即返回了
}
